package com.veal98.tree;

import com.veal98.bean.TreeNode;

public class MaximumBinaryTree_654 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        return buildTree(nums, 0, nums.length);
    }

    // 左闭右开
    private TreeNode buildTree(int[] nums, int left, int right) {
        // 没有元素了
        if (right - left < 1) {
            return null;
        }

        // 找到 nums[left:right) 中的最大值
        int max = left; // 最大值的下标
        for (int i = left + 1; i < right; i ++) {
            if (nums[i] > nums[max]) {
                max = i;
            }
        }

        // 根节点
        TreeNode root = new TreeNode(nums[max]);

        // 递归构造左子树
        root.left = buildTree(nums, left, max);
        // 递归构造右子树
        root.right = buildTree(nums, max + 1, right);

        return root;
    }


}
